package queue_stack.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @Author: yuisama
 * @Date: 2021/11/8 18:16
 * @Description:括号匹配问题
 * https://leetcode-cn.com/problems/valid-parentheses/
 */
public class Num20_isValid {
    public boolean isValid(String s) {
        // 遍历s的过程中将左括号入栈，碰到右括号查看栈顶元素是否匹配
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            }else {
                // 上来就是右括号，一定非法
                if (stack.isEmpty()) {
                    return false;
                }
                // 此时c是个右括号，查看栈顶元素
                char top = stack.pop();
                // 找反例
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
                if (c == ')' && top != '(') return false;
            }
        }
        return stack.isEmpty();
    }
}
